package DP;

/**
 * 有几道题，一个是字符串可以被分割为几个回文字符串
 * 第二个题是，求一个字符串连续最长回文长度
 */
public class PalindromeDP {

    /**
     * https://leetcode-cn.com/problems/palindrome-partitioning-ii/
     * 一个字符串 可以被分割为最少几个的回文
     * 一个字符串有多少回文串，其实可以变成一个二维数组
     * 然后，有一个i-j是否回文的数组，就可以开始做DP了，
     * 这个还是要背一下，很不错的题
     */
    public int minCut(String s) {
        char[] ss = s.toCharArray();
        int n = ss.length;
        if(n==0){
            return 0;
        }

        boolean[][] isPalin = calcPalin(ss);

        int[] dp = new int[n+1]; dp[0] = 0;
        for(int i=1; i<=n; i++){
            dp[i] = Integer.MAX_VALUE;
            for(int j=0; j < i; j++){
                if( isPalin[j][i-1] ){
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        //这里为什么 -1？ 上面已经是给 n+1了。
        return dp[n-1];

    }

    private boolean[][] calcPalin(char[] ss){
        int n = ss.length;
        boolean[][] isPalin = new boolean[n][n];

        //先循环判断奇数的，再判断偶数的回文
        int i,j,c;//中间字符位置，及回文的开始于结束

        //判断奇数的
        for(c=1; c<n; c++){
            i = c-1;
            j = c + 1;
            while ( i >=0 && j < n && ss[i] == ss[j] ){
                isPalin[i][j] = true;
                i--;j++;
            }
        }

        //判断偶数对称的
        for(c=0; c<n-1; c++){
            i=c;j=c+1;
            while ( i >=0 && j < n && ss[i] == ss[j] ){
                isPalin[i][j] = true;
                i--;j++;
            }
        }

        return isPalin;
    }

    /**
     * https://leetcode-cn.com/problems/longest-palindromic-subsequence/
     *
     * 这套题很不错！！！！！！！
     * 要特别注意这题
     *
     */
    public int longestPalindromeSubseq(String s) {
        char[] ss = s.toCharArray();
        int n = ss.length;
        if(n == 0) return 0;
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++) dp[i][i]=1;

        //这个很重要，因为结果就在右上角，或者左下角，不是传统的 右下角！！！！
        for(int i=1; i < n; i++){
            for(int j=i-1; j>=0 ; j--){
                if(ss[i] == ss[j]){
                    dp[i][j] = dp[i-1][j+1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i][j+1], dp[i-1][j]);
                }
            }
        }

        return dp[n-1][0];
    }


    public static void main(String[] args){
        PalindromeDP p = new PalindromeDP();
        int a=p.longestPalindromeSubseq("bbbab");
        System.out.println(a);

    }


}
